package binaryTree.review;

public class MergeSort3 {

    public int[] mergeSort(int[] nums){

        if (nums.length==0){
            return  null;
        }

        int[] temp = new int[nums.length];
        sort(nums,0, nums.length-1,temp);

        return  nums;

    }


    public  void  sort(int[] nums,int lo,int hi,int[] temp){
        //todo:这个等号很关键
        if (lo>=hi){
            return;
        }
        int mid=(lo+hi)/2;
        sort(nums,lo,mid,temp);
        sort(nums,mid+1,hi,temp);
        merge(nums,lo,mid,hi,temp);

    }

    public void merge(int[] nums,int lo,int mid,int hi,int[]temp){
        int i=0;
        int j=lo;
        int k=mid+1;
        while (j<mid+1&&k<=hi){

            if (nums[j]<=nums[k]){
                temp[i++]=nums[j++];
            }
            else {
                temp[i++]=nums[k++];
            }

        }
        while (j<mid+1){
            temp[i++]=nums[j++];
        }
        while (k<=hi){
            temp[i++]=nums[k++];
        }

        for (int l = 0; l <i ; l++) {
            nums[lo+l]=temp[l];

        }



    }

    public static void main(String[] args) {
        MergeSort3 mergeSort2 = new MergeSort3();
        int[] nums={2,5,3,1};
        int[] ints = mergeSort2.mergeSort(nums);
        for (int a :
                ints) {
            System.out.println(a);

        }
    }



}
